package com.fps.webshop.question.question0300_0399;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

/**
 * 350. 两个数组的交集 II
 * 
 * 给定两个数组，编写一个函数来计算它们的交集。
 * 
 * 示例 1：
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2,2]
 * 
 * 示例 2:
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[4,9]
 * 
 * 说明：
 * 		输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
 * 		我们可以不考虑输出结果的顺序。
 * 
 * 进阶：
 * 		如果给定的数组已经排好序呢？你将如何优化你的算法？
 * 		如果 nums1 的大小比 nums2 小很多，哪种方法更优？
 * 		如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
 */
public class Question350 {
	
	/**
	 * 第一次提交，先对两数组进行排序，再依次比较
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		2 ms	38.6 MB	Java	2021/08/12 10:48
	 */
	public static int[] intersect(int[] nums1, int[] nums2) {
		Arrays.sort(nums1);
		Arrays.sort(nums2);
		List<Integer> list = new ArrayList<>();
		int startA = 0;
		int startB = 0;
		while(startA<nums1.length&&startB<nums2.length) {
			if(nums1[startA]<nums2[startB]) {
				startA++;
			}else if(nums1[startA]>nums2[startB]) {
				startB++;
			}else {
				list.add(nums1[startA]);
				startA++;
				startB++;
			}
		}
		int[] a = new int[list.size()];
		for(int i=0;i<list.size();i++) {
			a[i]=list.get(i);
		}
		return a;
    }
	
	
	/**
	 * 第二次提交，使用两个HashMap解决。主要是处理无法进行排序的情况，比如进阶中的nums2无法全部加载到内存之类的
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		3 ms	38.3 MB	Java	2021/08/12 11:06
	 */
	public static int[] intersect2(int[] nums1, int[] nums2) {
		
		Map<Integer,Integer> num1Map = new HashMap<Integer,Integer>();
		Map<Integer,Integer> resultMap = new HashMap<Integer,Integer>();
		int num = 0;
		for(int a: nums1) {
			if(num1Map.get(a)!=null) {
				num1Map.put(a, num1Map.get(a)+1);
			}else {
				num1Map.put(a, 1);
			}
		}
		for(int a:nums2) {
			if(num1Map.get(a)!=null) {
				if(resultMap.get(a)!=null) {
					resultMap.put(a, resultMap.get(a)+1);
					num++;
				}else {
					resultMap.put(a, 1);
					num++;
				}
				if(num1Map.get(a)!=1) {
					num1Map.put(a, num1Map.get(a)-1);
				}else {
					num1Map.remove(a);
				}
			}
		}
		int[] result = new int[num];
		for(Entry<Integer, Integer> aa:resultMap.entrySet()) {
			for(int i=0;i<aa.getValue();i++) {
				result[num-1] = aa.getKey();
				num--;
			}
		}
		return result;
    }
	
	/**
	 * 第三次提交，尝试结合1、2，减少一个HashMap，增加一个List，但结果并不理想
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		3 ms	38.7 MB	Java	2021/08/12 11:10
	 */
	public static int[] intersect3(int[] nums1, int[] nums2) {
		Map<Integer,Integer> num1Map = new HashMap<Integer,Integer>();
		List<Integer> list = new ArrayList<>();
		for(int a: nums1) {
			if(num1Map.get(a)!=null) {
				num1Map.put(a, num1Map.get(a)+1);
			}else {
				num1Map.put(a, 1);
			}
		}
		for(int a:nums2) {
			if(num1Map.get(a)!=null) {
				list.add(a);
				if(num1Map.get(a)!=1) {
					num1Map.put(a, num1Map.get(a)-1);
				}else {
					num1Map.remove(a);
				}
			}
		}
		int[] result = new int[list.size()];
		for(int i=0;i<list.size();i++) {
			result[i]=list.get(i);
		}
		return result;
    }
	
	/**
	 * 第四次提交，在一的基础上改进，还是先对两数组进行排序，再依次比较，不同的是，直接使用int数组进行记录，不再使用List记录再转换成数组
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	38.5 MB	Java	2021/08/12 11:23
	 */
	public static int[] intersect4(int[] nums1, int[] nums2) {
		Arrays.sort(nums1);
		Arrays.sort(nums2);
		int[] result = new int[Math.max(nums1.length, nums2.length)];
		int resultLength = 0;
		int startA = 0;
		int startB = 0;
		while(startA<nums1.length&&startB<nums2.length) {
			if(nums1[startA]<nums2[startB]) {
				startA++;
			}else if(nums1[startA]>nums2[startB]) {
				startB++;
			}else {
				result[resultLength] = nums1[startA];
				startA++;
				startB++;
				resultLength++;
			}
		}
		return Arrays.copyOfRange(result, 0, resultLength);
    }
	
	public static void main(String[] args) {
		int[] nums1 = new int[] {1,2,2,1};
		int[] nums2 = new int[] {2,2};
		for(int a:intersect2(nums1,nums2)) {
			System.out.print(a+" ");
		}
	}
}
